package practise;

public class Partition {
    public static ListNode partition(ListNode pHead, int x) {
        if(pHead == null || pHead.next == null) {
            return pHead;
        }

        ListNode smallHead = new ListNode(0);// 小于 x 的链表
        ListNode bigHead = new ListNode(0);// 大于等于 x 的链表

        ListNode smallCur = smallHead;// 小链表的当前节点
        ListNode bigCur = bigHead;// 大链表的当前节点
        ListNode cur = pHead;// 原来列表的当前节点
        ListNode next = pHead.next;// 原来列表的下一个节点


        while(next != null) {
            if(cur.val < x) {
                smallCur.next = cur;
                smallCur = smallCur.next;
            } else {
                bigCur.next = cur;
                bigCur = bigCur.next;
            }
            cur = next;
            next = cur.next;
        }
        if(cur.val < x) {
            smallCur.next = cur;
            smallCur = smallCur.next;
        } else {
            bigCur.next = cur;
            bigCur = bigCur.next;
        }
        // 将小链表连接到大链表前
        smallCur.next = bigHead.next;
        // 将最后的指针置为 null
        bigCur.next = null;
        return smallHead.next;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(2);

        ListNode node1 = new ListNode(8);
        ListNode node2 = new ListNode(6);
        node.next = node1;
        node1.next = node2;
       ListNode ret =  partition(node, 9);
    }
}
